/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package push2java;

import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 *
 * @author Admin
 */
public class Evolution {

    private static final int members = 1000;
    private static final int points = 20;
    private static final int generations = 1000;
    private static final int rounds = 10;
    private FitnessFunction fitnessFunction;
    private int generation = 0;
    private Random random = new Random();
    private List<PushProgram> population;
    private PushProgram best;

    public Evolution(FitnessFunction fitnessFunction) {
        this.fitnessFunction = fitnessFunction;
        population = new LinkedList<PushProgram>();
        for (int i = 0; i < members; i++) {
            population.add(generate(points));
        }
    }

    public void step() {
        if (!finished()) {
            select();
            reproduce();
            mutate();
            assert population.size() == members;
            generation++;
            System.err.println(generation + " / " + generations);
        }
    }

    public boolean finished() {
        return generation >= generations;
    }

    public PushProgram getBest() {
        return best;
    }

    private void updateFitness(PushProgram program) {
        program.fitness = fitnessFunction.fitness(program);
        if (best == null || program.fitness > best.fitness) {
            best = new PushProgram(program);
            System.err.println(best.fitness);
        }
    }

    private void select() {
        Map<PushProgram, Integer> scores = new HashMap<PushProgram, Integer>();
        for (PushProgram program : population) {
            scores.put(program, 0);
        }
        // for each round
        for (int round = 0; round < rounds; round++) {
            Map<PushProgram, Integer> newScores = new HashMap<PushProgram, Integer>();
            // pair up programs of equal score and compete
            for (int score = 0; score <= round; score++) {
                List<PushProgram> bracket = new ArrayList<PushProgram>();
                for (PushProgram program : scores.keySet()) {
                    if (scores.get(program) == score) {
                        bracket.add(program);
                    }
                }
                Collections.shuffle(bracket, random);
                while (bracket.size() > 0) {
                    if (bracket.size() == 1) {
                        PushProgram p = bracket.remove(0);
                        newScores.put(p, score + 1);
                    } else {
                        PushProgram p1 = bracket.remove(0);
                        PushProgram p2 = bracket.remove(0);
                        updateFitness(p1);
                        updateFitness(p2);
                        if (p1.fitness > p2.fitness) {
                            newScores.put(p1, score + 1);
                            newScores.put(p2, score);
                        } else {
                            newScores.put(p2, score + 1);
                            newScores.put(p1, score);
                        }
                    }
                }
            }
            scores.clear();
            scores.putAll(newScores);
        }
        population.clear();
        population.addAll(scores.keySet());
    }

    private void reproduce() {
        List<PushProgram> newPopulation = new LinkedList<PushProgram>();
        while (newPopulation.size() < members) {
            PushProgram p1 = population.get(random.nextInt(population.size()));
            PushProgram p2 = population.get(random.nextInt(population.size()));
            newPopulation.add(p1);
            newPopulation.add(p2);
            PushProgram c1 = new PushProgram(p1);
            PushProgram c2 = new PushProgram(p2);
            crossover(c1, c2);
            newPopulation.add(c1);
            newPopulation.add(c2);

        }
        population = newPopulation;
        assert population.size() == members;
    }

    private void crossover(PushProgram p1, PushProgram p2) {
        int start = random.nextInt(p1.expressions.size());
        int end = random.nextInt(p1.expressions.size());
        if (start > end) {
            int tmp = start;
            start = end;
            end = tmp;
        }
        List<Expression> subExpr1 = p1.expressions.subList(start, end);
        List<Expression> subExpr2 = p2.expressions.subList(start, end);
        List<Expression> tmp = new LinkedList<Expression>();
        tmp.addAll(subExpr1);
        subExpr1.clear();
        subExpr1.addAll(subExpr2);
        subExpr2.clear();
        subExpr2.addAll(tmp);
        assert p1.expressions.size() == points;
        assert p1.expressions.size() == points;
    }

    private void mutate() {
        List<PushProgram> newPopulation = new LinkedList<PushProgram>();
        for (PushProgram program : population) {
            while (random.nextFloat() < 0.1) {
                int index = random.nextInt(program.expressions.size());
                program.expressions.set(index, getRandomExpression());
            }
            newPopulation.add(program);
        }
        population = newPopulation;
    }

    private Expression getRandomExpression() {
        if (random.nextFloat() < 0.2) {
            return new Expression(random.nextFloat(), Type.Literal.FLOAT);
        } else if (random.nextFloat() < 0.2) {
            return new Expression(random.nextBoolean(), Type.Literal.BOOLEAN);
        } else {
            List<Method> instructions = PushProgram.getInstructions();
            Method method = instructions.get(random.nextInt(instructions.size()));
            return new Expression(method);
        }
    }

    private PushProgram generate(int points) {
        List<Expression> expressions = new ArrayList<Expression>();
        for (int i = 0; i < points; i++) {
            expressions.add(getRandomExpression());
        }
        return new PushProgram(expressions);
    }
}
